import com.sun.source.tree.Tree;

import java.util.*;

/**
 * 搜索树
 * 若他的左节点部位空，那么他的左节点小于根节点
 * 若他的头节点不为空，呢么他的右节点大与根节点
 */
public class map {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root = null;

    //插入
    public void push(TreeNode root, int val) {
        if (root == null) {//没有节点
            this.root = new TreeNode(val);
            return;
        }
        if (root.val > val) {// val小于更往左放
            if (root.left == null) {//要写个节点为空彩纺
                root.left = new TreeNode(val);
                return;
            } else {//玩左边递归
                push(root.left, val);
            }
        } else {//value大于根放右边
            if (root.right == null) {

                root.right = new TreeNode(val);
                return;
            } else {//往右边递归
                push(root.right, val);
            }
        }
    }

    //插入
    public void insert(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
        }

        if (root.val > val) {//根节点大于val要往跟小的左节点去插入
            if (root.left == null || root.left.val < val) { // root.left.val < val < root.val 插入
                TreeNode tmp = root.left;
                root.left = new TreeNode(val);
                root.left.left = tmp;
                return;
            } else {
                insert(root.left, val);//向左继续递
            }
        } else {
            if (root.right == null || root.right.val > val) {//说明遍历到最后一个
                TreeNode tmp = root.right;
                root.right = new TreeNode(val);
                root.right.right = tmp;
                return;
            } else {
                insert(root.right, val);
            }
        }

    }

    //删除
    public Boolean del(TreeNode root, int key){
        //找到要删除的数
        TreeNode prev = root;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > key) {
                prev = cur;
                cur = cur.left;
            } else if (cur.val < key) {
                prev = cur;
                cur = cur.right;
            } else {//找到了
                break;
            }
        }

        if (cur == null) {
            return false;
        }//说明没找到
        //删除
        if (cur.left == null) {//cur单边为空的情况
            if (cur == prev) {
                cur = cur.right;
                this.root = cur;
            } else if (prev.right == cur) {
                prev.right = cur.right;
            } else {
                prev.left = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == prev) {
                cur = cur.left;
                this.root = cur;
            } else if (prev.right == cur) {
                prev.right = cur.left;
            } else {
                prev.left = cur.left;
            }
        } else {//两边都不为空 替换法删除
            //找到左边树往下的最右边的值去替换
            TreeNode cur1 = cur.left;
            TreeNode prev1 = cur.left;
            while (cur1.right != null) {//找到最后一个
                cur1 = cur1.right;
            }
            if (cur1 == prev1) {
                cur.val = cur1.val;
                cur.left = cur1.left;
            } else {
                cur.val = cur1.val;
                prev1.right = cur1.left;
            }
        }
        return true;
    }

    private void swapChildVal(TreeNode root) {
        int tmp = root.left.val;
        root.left.val = root.right.val;
        root.right.val = tmp;
    }

    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //层序遍历
    public List<List<String>> levelOrder(TreeNode root) {
        List<List<String>> arr = new LinkedList();
        if (root == null) {
            return arr;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//决定这一层要循环多少次
            List<String> tmpL = new LinkedList<>();//储存这一层的数字
            while (size != 0) {
                TreeNode tmp = queue.poll();//从头开始出并存入该值和将这个更根节点的俩子节点存入
                if (tmp != null) {
                    tmpL.add(tmp.val + "");
                    queue.offer(tmp.left);
                    queue.offer(tmp.right);
                } else {
                    tmpL.add("null");
                }
                size--;
            }
            arr.add(tmpL);
        }
        return arr;
    }//现在这个会在没有节点的地方记上null

    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> arr = new LinkedList();
        if (root == null) {
            return arr;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//决定这一层要循环多少次
            List<Integer> tmpL = new LinkedList<>();//储存这一层的数字
            while (size != 0) {
                TreeNode tmp = queue.poll();//从头开始出并存入该值和将这个更根节点的俩子节点存入
                tmpL.add((Integer) tmp.val);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
            }
            arr.add(tmpL);
        }

//        Collections.reverse(arr);//从下到上打印
        return arr;
    }

    public Boolean isEmpty() {
        return this.root == null;
    }
}
class text{
    public static void main(String[] args) {
        Map<String, Integer> hh = new HashMap<>();
        hh.put("aa",1);

    }
    public static void main2(String[] args) {
        int[] arr = {8, 2, 9, 0, 7, 8, 9, 2, 8, 9};
        map one = new map();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
//            one.push(one.root, random.nextInt(10 ));
            one.push(one.root, i);
        }
        List<List<String>> hh = one.levelOrder(one.root);
        System.out.println(Arrays.toString(hh.toArray()));
    }
    public static void maina(String[] args) {
        //[[8], [2, 9], [0, 7, 8, 9], [2, 8, 9]]
        int[] arr = {8, 2, 9, 0, 7, 8, 9, 2, 8, 9};
        map one = new map();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
//            one.push(one.root, random.nextInt(10 ));
            one.push(one.root, arr[i]);
        }
        List<List<String>> hh = one.levelOrder(one.root);
        System.out.println(Arrays.toString(hh.toArray()));
//        one.insert(one.root,1);
//        one.insert(one.root,0);
//        one.insert(one.root,-1);
//        hh = one.levelOrder(one.root);
//        System.out.println(Arrays.toString(hh.toArray()));
//        one.preOrder(one.root);
        one.del(one.root,8);
        one.del(one.root,8);
        one.del(one.root,8);
        one.del(one.root,2);
        one.del(one.root,2);
        one.del(one.root,0);
        one.del(one.root,9);
        one.del(one.root,9);
        one.del(one.root,9);
        one.del(one.root,7);
        hh = one.levelOrder(one.root);
        System.out.println("===");
        System.out.println(Arrays.toString(hh.toArray()));

    }
}